package day23_30;

import java.util.*;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/1 15:47
 * @Version 1.0
 */
//public class Solution {
//    public static List<Integer> findSubstring(String s, String[] words) {
//        //1. 使用哈希表存储words中各个字符的索引
//        HashMap<String, Integer> map = new HashMap<>();
//
//        //2. 使用哈希表存储并判断当前子串是否为words的所有字符组合，已经是否有其他字符
//        HashSet<Integer> set = new HashSet();
//
//        //记录左右索引值
//        List<Integer> res = new LinkedList<>();
//        res.add(0);
//
//        //记录单词长度
//        int wordLength = words[0].length();
//
//        for (int i = 0; i < words.length; i++) {
//            map.put(words[i], i);
//        }
//
//        int slow = 0;
//        int fast = 0;
//        while (fast < s.length()) {
//            while (fast - slow < wordLength) {
//                fast++;
//            }
//            String sub = s.substring(slow, fast);
//            Integer idx = map.get(sub);
//            if (idx == null){
//                slow = fast;
//                set.clear();
//                continue;
//            }
//
//            if (set.size() == words.length){
//                res.add(slow);
//                set.clear();
//            }
//
//            if (set.isEmpty()){
//                set.add(idx);
//
//            }else {
//
//            }
//            slow = fast;
//
//
//        }
//
//        return res;
//    }
//
//    public static void main(String[] args) {
//        String s = "barfoofoobarthefoobarman";
//        String[] words = {"foo", "bar", "the"};
//        List<Integer> res = findSubstring(s, words);
//        System.out.println(res);
//    }
//}


public class Solution {

    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> res = new ArrayList<>();

        Map<String, Integer> map = new HashMap<>();

        if (words == null || words.length == 0)
            return res;

        for (String word : words)
            map.put(word, map.getOrDefault(word, 0) + 1);

        int sLen = s.length(), wordLen = words[0].length(), count = words.length;

        int match = 0;

        for (int i = 0; i < sLen - wordLen * count + 1; i++) {

            //得到当前窗口字符串
            String cur = s.substring(i, i + wordLen * count);
            Map<String, Integer> temp = new HashMap<>();
            int j = 0;

            for (; j < cur.length(); j += wordLen) {

                String word = cur.substring(j, j + wordLen);
                // 剪枝
                if (!map.containsKey(word))
                    break;

                temp.put(word, temp.getOrDefault(word, 0) + 1);
                // 剪枝
                if (temp.get(word) > map.get(word))
                    break;
            }

            if (j == cur.length())
                res.add(i);
        }

        return res;
    }
}